package leetcode.pre50;


import offerbook.Code13_DeleteListNode;
import offerbook.Code15_FindKthToTaikInList;
import offerbook.Code57_DeleteRepeatNode;
import utils.ListNode;
import utils.ListUtil;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * <p>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * <p>
 * 分析见{@link Code15_FindKthToTaikInList}
 * <p>
 * 拓展见{@link Code13_DeleteListNode}
 * <p>
 * 进阶见{@link Code57_DeleteRepeatNode}
 *
 * @date 2019/11/21 0021 上午 10:17
 */
public class Code19_DeleteKthToTailInList {

    /**
     * 方式1：遍历一遍链表，然后计数去扫描
     * 注意过程判断长度是否达到n,注意删除是头结点的情况
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0) {
            return head;
        }
        //TODO 先判断是否有环
        int len = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            len++;
        }
        //如果n超过了len长度，非法
        if(n >= len){
            return n > len ? head: head.next;
        }
        //倒数第n个，就是正属第 len + 1 - n
        n = len + 1 - n;
        cur = head;
        n--;//head处先自减1
        //如删除第3个，就要先找到第2个。
        while (n != 1){
            cur = cur.next;
            n--;
        }
        //当前的cur是要删除节点的前驱节点
        cur.next = cur.next.next;
        return head;
    }

    /**
     * 方式2：倒数第n是离最后一个间隔为n的点。
     * 设定两个指针p1,p2。让p2先走，当p2 - p1 + 1 = n,p2与p1一起走。
     * 也就是p2与p1之间距离是n。(包含自身) 。
     * 当p2=tail，p1就是倒数第n个点。当n = 1，p2=p1=tail
     *
     * 注意过程判断长度是否达到n,注意删除是头结点的情况。
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head == null || n <= 0) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        int count = 1;
        while (count < n){
            p2 = p2.next;
            count ++;
            //整个链表长度小于n
            if(p2 == null){
                return head;
            }
        }
        //p2现在是第n个节点，p1是第1个节点

        //如果p2是最后一个节点，也就是要删除的是头结点
        if(p2.next == null){
            return p1.next;
        }

        //循环结束后p2是倒数第二个节点，p1是要删除节点的前驱节点
        while (p2.next.next!=null){
            p1 = p1.next;
            p2 = p2.next;
        }

        //p1是要删除的前驱
        p1.next = p1.next.next;
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        removeNthFromEnd(head, 2);
        ListUtil.printLinkedList(head);
    }
}
